package com.liunian.algorithmstudy.stackandqueue;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class MaxSlidingWindow239 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<>();
        int[] results = new int[nums.length - k + 1];
        for (int i = 0; i < k; i++) {
            push(nums[i], deque);
        }
        int index = 0;
        results[index++] = getMaxValue(deque);
        results[0] = deque.peekFirst();
        for (int i = k; i < nums.length; i++) {
            pop(nums[i - k], deque);
            push(nums[i], deque);
            int maxValue = getMaxValue(deque);
            results[index++] = maxValue;
        }
        return results;
    }

    public void push(int val, Deque<Integer> deque) {
        while (!deque.isEmpty() && deque.peekLast() < val) {
            deque.pollLast();
        }
        deque.addLast(val);
    }

    public void pop(int val, Deque<Integer> deque) {
        if (!deque.isEmpty() && deque.peekFirst() == val) {
            deque.pollFirst();
        }
    }

    public int getMaxValue(Deque<Integer> deque) {
        return deque.peekFirst();
    }

    public static void main(String[] args) {
        MaxSlidingWindow239 maxSlidingWindow = new MaxSlidingWindow239();
        System.out.println(Arrays.toString(maxSlidingWindow.maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
    }

}
